func lastStoneWeightII(stones []int) int {
    /*
        1. 确定dp数组的含义
            dp[i] 表示容量为i的背包，可以装的最多的石头重量

        2. 确定递推公式
            dp[i] = max(dp[i], dp[i-weight[i]] + value[i])

        3. 初始化dp数组，都初始化为0即可

        4.确定遍历顺序，先遍历物品再遍历背包容量从大到小

        5. 推理递推公式
    */
    var sum int
    var packageSize int
    for i:=0; i<len(stones); i++ {
        sum += stones[i]
    }
    packageSize = sum / 2
    dp := make([]int, packageSize+1)
    for i:=0; i<len(stones); i++ {
        for j:=packageSize; j>=stones[i]; j--{
            dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
        }
    }
    leftWeight := sum - dp[packageSize]
    rightWeight := sum - leftWeight
    return abs(leftWeight-rightWeight)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}




